package com.mlh.dp.old;

// 题目：
// 给你一个由 n 个数对组成的数对数组 pairs ，其中 pairs[i] = [lefti, righti] 且 lefti < righti 。
// 现在，我们定义一种 跟随 关系，当且仅当 b < c 时，数对 p2 = [c, d] 才可以跟在 p1 = [a, b] 后面。我们用这种形式来构造数对链 。
// 找出并返回能够形成的 最长数对链的长度 。
// 你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。
// 举例：
// 输入：pairs = [[2,3],[3,4],[4,5]]
// 输出：2
// 解释：最长的数对链是 [1,2] -> [3,4] 。

import java.util.Arrays;

public class FindLongestChain {

    public static void main(String[] args) {
        int[][] test1 ={{1,2},{7, 8},{4, 5}} ;
    }


    //最长数链对肯定是严格递增的
    //dp解法和最长递增子序列一样
    //也可以用二分
    public static int method1(int[][]pairs){
        return 0;
    }

    //贪心解法
    //要挑选最长数对链的第一个数对时，最优的选择是挑选第二个数字最小的，这样能给挑选后续的数对留下更多的空间。
    // 挑完第一个数对后，要挑第二个数对时，也是按照相同的思路，是在剩下的数对中，第一个数字满足题意的条件下，挑选第二个数字最小的。
    // 按照这样的思路，可以先将输入按照第二个数字排序，然后不停地判断第一个数字是否能满足大于前一个数对的第二个数字即可。
    public int method2(int[][] pairs) {
        int curr = Integer.MIN_VALUE, res = 0;
        //这是这段代码的作用是对二维数组 pairs 进行排序。
        // 它使用了 Arrays 类的 sort 方法，并通过 lambda 表达式提供了一个自定义的比较器。
        // 具体来说，它按照每个元素的第二个值（索引为 1）进行升序排序。
        // 排序后，pairs 数组中的子数组将按照第二个元素的大小进行排列。
        //这里的a 和 b相当于取出来的一维数组了
        Arrays.sort(pairs, (a, b) -> a[1] - b[1]);
        for (int[] p : pairs) {
            if (curr < p[0]) {
                curr = p[1];
                res++;
            }
        }
        return res;
    }

    //这是我改的贪心的方法
    //思想是数组的第一个元素越大，前面越能装下数组，因此以第一个元素进行排序，从大到小来进行遍历
    public int method3(int[][] pairs) {
        int curr = Integer.MAX_VALUE, res = 0;
        Arrays.sort(pairs, (a, b) -> a[0] - b[0]);
       for(int i=pairs.length-1;i>=0;i--){
           if(pairs[i][1]<curr){
               curr=pairs[i][0];
               res++;
           }
       }
        return res;
    }

}
